//
//  Problem1414.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/24.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1414. 和为 K 的最少斐波那契数字数目
 给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
 斐波那契数字定义为：
     F1 = 1
     F2 = 1
     Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
     数据保证对于给定的 k ，一定能找到可行解。
 示例 1：
     输入：k = 7
     输出：2
     解释：斐波那契数字为：1，1，2，3，5，8，13，……
     对于 k = 7 ，我们可以得到 2 + 5 = 7 。
 示例 2：
     输入：k = 10
     输出：2
     解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
 示例 3：
     输入：k = 19
     输出：3
     解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。

 提示：
    1 <= k <= 10^9
 */
@objcMembers class Problem1414: NSObject {
    func solution() {
        print(findMinFibonacciNumbers(7))
        print(findMinFibonacciNumbers(10))
        print(findMinFibonacciNumbers(19))
    }
    
    /*
     贪心法：
     要想数量最少，那么就让每个值近可能的大，每次取离值最近的斐波那契数字 -> 满足局部
     1: 创建一个数组，存储斐波那契数字，知道 这个值 > k
     2: 取离k最近的斐波那契数字n，然有 k -= n, 继续
     */
    func findMinFibonacciNumbers(_ k: Int) -> Int {
        var list: [Int] = [1, 1]
        while list.last! < k {
            list.append(list.last! + list[list.count-2])
        }
        print(list)
        
        var tk = k
        var result = 0
        for i in (0..<list.count).reversed() {
            if tk == 0 {
                break
            }
            if list[i] <= tk {
                result += 1
                tk -= list[i]
            }
        }
        return result
    }
}
